/**
 * @author 徐楠
 * @date 2022/5/18 7:09
 * @version 1.0
 */

package com.xunan.likou;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class MatchTheLongestWordInTheDictionaryByDeletingLetters {
    public static void main(String[] args) {
        String s = "abpcplea";
        List<String> list = Arrays.asList("ale", "apple", "monkey", "plea");
        String longestWord = findLongestWord(s, list);
        System.out.println(longestWord);
    }

    public static String findLongestWord(String s, List<String> dictionary) {
        //排序
        //长度不同的字符串，按照字符串长度排倒序；
        //长度相同的，则按照字典序排升序。
        Collections.sort(dictionary, (a, b) -> {
            if (a.length() != b.length()) return b.length() - a.length();
            return a.compareTo(b);
        });

        /**
         * 使用两个指针 i 和 j 分别代表检查到 s 和 dictionary[x] 中的哪位字符；
         * 当 s[i] != dictionary[x][j]，我们使 i 指针右移，直到找到 s 中第一位与 dictionary[x][j] 对得上的位置，然后当 i 和 j 同时右移，匹配下一个字符；
         * 重复步骤 22，直到整个 dictionary[x] 被匹配完。
         */
        int n = s.length();
        for (String ss : dictionary) {
            int m = ss.length();
            int i = 0;
            int j = 0;
            while (i < n && j < m) {
                if (s.charAt(i) == ss.charAt(j)) {
                    j++;
                }
                i++;
            }
            if (j == m) {
                return ss;
            }
        }
        return "";
    }

}
